package com.wc.alorithm.string.suffixArray;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @Author congege
 * @Description 后缀数组
 * @Date Created in 2023/12/13-22:36
 */
public class Main2 {
    static int N = (int) (2e6 + 10);
    static char[] s = new char[N];
    // 存数的桶
    static int[] buc = new int[N];
    static int[] repeatS = new int[N];
    // sa[i] 表示第i个的字典序是从sa[i]位置往后
    static int[] sa = new int[N];
    static int[] repeatSa = new int[N];
    // height[i] 表示sa[i]与sa[i-1]的最长公共前缀，lcp(suff(sa[i],sa[i-1])
    static int[] height = new int[N];
    // rk[i] 表示以i开头的后缀子串排第几
    static int[] rk = new int[N];
    // 字符串长度
    static int n;
    // 字符的值域
    static int m;

    // 计算出sa
    private static void getSa() {
        // 根据第一关键字放入桶内
        for (int i = 1; i <= n; i++) {
            buc[repeatS[i] = s[i]]++;
        }
        // 利用前缀和，为了排序
        for (int i = 1; i <= m; i++) {
            buc[i] += buc[i - 1];
        }
        // 将第一次排序结果存入sa,要倒置过来
        for (int i = n; i >= 1; i--) {
            sa[buc[repeatS[i]]--] = i;
        }

        // 根据倍增的思想，根据第二关键字排序，再根据第一关键字恢复
        for (int k = 1; k <= n; k <<= 1) {
            // 将桶清空
            Arrays.fill(buc, 0);
            // 复制上次的sa
            for (int i = 1; i <= n; i++) {
                repeatSa[i] = sa[i];
            }
            // 根据第二关键字加入到桶中
            for (int i = 1; i <= n; i++) {
                // 根据第一次排序的结果来进行第而关键字排序
                buc[repeatS[repeatSa[i] + k]]++;
            }
            // 前缀和
            for (int i = 1; i <= m; i++) {
                buc[i] += buc[i - 1];
            }
            // 取出桶中的内容
            for (int i = n; i >= 1; i--) {
                sa[buc[repeatS[repeatSa[i] + k]]--] = repeatSa[i];
            }
            // 再按照第一关键字排序
            Arrays.fill(buc, 0);
            // 复制上次排序结果
            for (int i = 1; i <= n; i++) {
                repeatSa[i] = sa[i];
            }
            // 根据第一关键字放入桶中
            for (int i = 1; i <= n; i++) {
                buc[repeatS[repeatSa[i]]]++;
            }
            // 前缀和
            for (int i = 1; i <= m; i++) {
                buc[i] += buc[i - 1];
            }
            // 根据第一关键字将桶中内容取出
            for (int i = n; i >= 1; i--) {
                sa[buc[repeatS[repeatSa[i]]]--] = repeatSa[i];
            }

            // 存下字符串
            for (int i = 1; i <= n; i++) {
                repeatSa[i] = repeatS[i];
            }
            // 重新给桶编号,我们是不需要所有桶的,有些空的桶是可以优化掉的
            m = 0;
            for (int i = 1; i <= n; i++) {
                // 判断第一关键字和第二关键字是不是相同的
                if (repeatSa[sa[i]] == repeatSa[sa[i - 1]] && repeatSa[sa[i] + k] == repeatSa[sa[i - 1] + k]) {
                    repeatS[sa[i]] = m;
                } else {
                    repeatS[sa[i]] = ++m;
                }

            }
            // 所有字符全不相同的时候，说明已经达到排序任务了，只需要一次排序
            if (m == n) {
                break;
            }
        }
    }

    private static void getHeight() {
        // 根据已经排好的sa
        for (int i = 1; i <= n; i++) {
            rk[sa[i]] = i;
        }
        // 根据rk来计算height的 height[rk[i]] >= height[rk[i-1]] - 1
        for (int i = 1, k = 0; i <= n; i++) {
            if (rk[i] == 1) {
                continue;
            }
            if (k > 0) {
                k--;
            }
            int j = sa[rk[i] - 1];
            while (k + i < n && k + j <= n && s[k + i] == s[k + j]) {
                k++;
            }
            height[rk[i]] = k;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        s = (" " + sc.nextLine()).toCharArray();
        n = s.length - 1;
        m = 'a' + 25;
        getSa();
        StringBuffer ans = new StringBuffer();
        ans.append(sa[1]);
        for (int i = 2; i <= n; i++) {
            ans.append(' ');
            ans.append(sa[i]);
        }
        System.out.println(ans);
    }
}
